package com.unionfind;

import java.util.HashMap;
import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-10-21 09:48
 */
public class GenericUnionFind<V> implements UnionFind<V> {

    private static class Node<V>{

        Node<V> parent;
        V val;
        int rank;

        public Node(V val) {

            this.val = val;
            this.parent = this;
            this.rank = 1;
        }

        @Override
        public String toString() {

            StringBuilder sb = new StringBuilder(val.toString());

            return sb.toString();
        }
    }

    private HashMap<V,Node<V>> nodeContains;

    public GenericUnionFind() {

        nodeContains = new HashMap<>();
    }

    public void addNode(V v) {

        if (nodeContains.containsKey(v)) {
            return;
        }
        nodeContains.put(v,new Node<>(v));
    }

    @Override
    public V find(V v) {

        Node<V> node = nodeContains.get(v);

        if (Objects.isNull(node)) {
            return null;
        }

        while (!Objects.equals(node.val, node.parent.val)) {

            node.parent = node.parent.parent;
            node = node.parent;
        }

//        while (!Objects.equals(node.val,node.parent.val)) {
//
//            node = node.parent;
//        }

        return node.val;
    }


    @Override
    public void union(V v1, V v2) {

        V rv1 = find(v1);
        V rv2 = find(v2);

        if (Objects.isNull(rv1) || Objects.isNull(rv2)) {

            return;
        }

        if (Objects.equals(rv1,rv2)) {

            return;
        }

        Node<V> n1 = findNode(rv1);
        Node<V> n2 = findNode(rv2);

        if (n1.rank < n2.rank) {

            n1.parent = n2;
        }else if (n1.rank > n2.rank) {

            n2.parent = n1;
        }else {

            n1.parent = n2;
            n2.rank++;
        }
    }

    @Override
    public boolean isSame(V v1, V v2) {

        return Objects.equals(find(v1),find(v2));
    }

    private Node<V> findNode(V v) {

        return nodeContains.get(v);
    }

    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();


        return sb.toString();
    }
}
